The Generalized Bergman game

Abstract: P. Baird-Smith A. Epstein, K. Flint, and S. J. Miler (2018) created the \emph{Zeckendorf Game}, a two-player game which takes as an input a positive integer $n$ and, using moves related to the Fibonacci recurrence relation, outputs the unique decomposition of $n$ into a sum of non-consecutive Fibonacci numbers. Following this work and that of G. Bergman (1957), which proved the existence and uniqueness of such $\varphi$-decompositions, we formulate the \emph{Bergman Game} which outputs the unique decomposition of $n$ into a sum of non-consecutive powers of $\varphi$, the golden mean.

We then formulate \emph{Generalized Bergman Games}, which use moves based on an arbitrary non-increasing positive linear recurrence relation and output the unique decomposition of $n$ into a sum of non-adjacent powers of $\beta$, where $\beta$ is the dominating root of the characteristic polynomial of the chosen recurrence relation. We prove that the longest possible Generalized Bergman game on an initial state $S$ with $n$ summands terminates in $\Theta(n^2)$ time, and we also prove that the shortest possible Generalized Bergman game on an initial state terminates between $\Omega(n)$ and $O(n^2)$ time. We also show a linear bound on the maximum length of the tuple used throughout the game.

This is joint work with Benjamin Baily, Justine Dell, Irfan Durmic, Henry Fleischmann, Isaac Mijares, Steven J. Miller, Ethan Pesikoff, Alicia Smith Reina, and Yingzi Yang.

number theory

Audience: researchers in the discipline

( paper | slides )

Combinatorial and additive number theory (CANT 2022)